package org.zlb.algorithm.sort;

/**
 * 堆排序
 * 堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
 * 或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
 *
 * @author zhoulingbo
 * @date 2021/7/16 15:02
 */
public class HeapSort extends AbstractSort {

    @Override
    public void sort(int[] arr) {
        for (int i = arr.length / 2; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }

        for (int i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            adjustHeap(arr, 0, i);
        }
    }

    void adjustHeap(int[] arr, int parent, int length) {
        int temp = arr[parent];
        int child = 2 * parent + 1;

        while (child < length) {
            if (child + 1 < length && arr[child] < arr[child + 1]) {
                child ++;
            }

            if (temp >= arr[child])
                break;

            arr[parent] = arr[child];

            parent = child;
            child = 2 * child + 1;
        }

        arr[parent] = temp;
    }

}
